package algor

type NTreeNode struct {
	Val      int
	Children []*NTreeNode
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 后序遍历
func PostorderNTreeNode(root *NTreeNode) []int {
	if root == nil {
		return nil
	}
	result := make([]int, 0, 1)
	postorderNTreeNode(root, &result)
	// result = append(result, root.Val)
	// for _, v := range root.Children {
	// 	result = append(result, PreorderNTreeNode(v)...)
	// }
	return result
}

func postorderNTreeNode(root *NTreeNode, results *[]int) {
	if root == nil {
		return
	}
	for _, v := range root.Children {
		postorderNTreeNode(v, results)
	}
	*results = append(*results, root.Val)
}

// 广度优先遍历
func BreathFirstTraverse(root *NTreeNode) []int {
	result := make([]int, 0, 1)

	stack := NewQueueNTreeNode(root) // 辅助栈
	for stack.Len() != 0 {
		n := stack.Pull()
		result = append(result, n.Val)
		stack.Push(n.Children...)
	}
	return result
}

// 深度优先遍历
func DepthOederTraverse(root *NTreeNode) []int {
	result := make([]int, 0, 1)

	stack := NewQueueNTreeNode(root)
	for stack.Len() != 0 {
		n := stack.Pull()
		result = append(result, n.Val)
		for i := range n.Children {
			stack.Push(n.Children[len(n.Children)-1-i])
		}
	}
	return result
}

// 构建树

// [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
// []int{1, 0, 2, 3, 4, 5, 0, 0, 6, 7, 0, 8, 0, 9, 10, 0, 0, 11, 0, 12, 0, 13, 0, 0, 14}
func BuildNTree(arr []int) *NTreeNode {
	if len(arr) == 0 {
		return nil
	}

	root := &NTreeNode{
		Val: arr[0],
	}
	q := NewQueueNTreeNode(root)
	idx := 1

	for q.Len() > 0 {
		qhead := q.Pull()
		if idx == len(arr) || arr[idx] != 0 {
			continue
		}

		idx++
		children := make([]*NTreeNode, 0)

		for idx < len(arr) && arr[idx] != 0 {
			n := &NTreeNode{
				Val: arr[idx],
			}
			children = append(children, n)
			q.Push(n)

			idx++
		}

		if len(children) != 0 {
			qhead.Children = children
		}
	}

	return root
}

// 有序数组构建平衡二叉搜索树
func SortedArrayToBST(nums []int) *TreeNode {
	return sortedArrayToBSTHelper(nums, 0, len(nums)-1)
}

func sortedArrayToBSTHelper(nums []int, left, right int) *TreeNode {
	if left > right {
		return nil
	}
	mid := (left + right) / 2
	root := &TreeNode{Val: nums[mid]}
	root.Left = sortedArrayToBSTHelper(nums, left, mid-1)
	root.Right = sortedArrayToBSTHelper(nums, mid+1, right)
	return root
}
